package com.company;

import java.util.LinkedList;
import java.util.Queue;

public class BynaryTree {

    class BynaryNode{
        int val;
        BynaryNode left;
        BynaryNode right;
        public BynaryNode(int val) {
            this.val = val;
        }
        public BynaryNode(int val, BynaryNode left, BynaryNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public void preOrder(BynaryNode root){
        if(root == null){
            return;
        }
        System.out.println(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }

    public void bfs(BynaryNode root){
        Queue<BynaryNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            BynaryNode node = queue.poll();
            System.out.println(node.val);
            if(node.left != null){
                queue.offer(node.left);
            }
            if(node.right != null){
                queue.offer(node.right);
            }
        }
    }

    public static void main(String[] args) {
        int n = 10;
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = i;
        }
        BynaryTree tree = new BynaryTree();
        BynaryNode root = tree.construct(arr);
        tree.bfs(root);
        tree.preOrder(root);
    }

    public BynaryNode construct(int[] arr){
        BynaryNode[] nodes = new BynaryNode[arr.length];
        for (int i = 0; i < arr.length; i++){
            nodes[i] = new BynaryNode(arr[i]);
        }
        for(int i = 0; i < nodes.length / 2; i++){
            if(i == 0){
                nodes[i].left = 1 < arr.length?nodes[1]: null;
                nodes[i].right = 2 < arr.length?nodes[2]: null;
            }else{
                int index = 2 * i + 1;
                if(index >= arr.length){
                    break;
                }
                nodes[i].left = nodes[2 * i + 1];
                index = 2 * i + 2;
                if(index < arr.length){
                    nodes[i].right = nodes[index];
                }
            }
        }
        return nodes[0];
    }
}
